МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІКТА, кафедра “Захист інформації”
ЗВІТ
З ЛАБОРАТОРНОЇ РОБОТИ № 3
З КУРСУ “ КОМП’ЮТЕРНІ МЕТОДИ ДОСЛІДЖЕННЯ ІНФОРМАЦІЙНИХ ПРОЦЕСІВ ТА СИСТЕМ ”
НА ТЕМУ: “ ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ
ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ“
Варіант 19
Мета роботи – ознайомлення з ітераційними методами розв’язування систем лінійних алгебраїчних рівнянь.
Короткі теоретичні відомості
Метод простої ітерації.
Нехай дано лінійну систему
(1)
Розглянемо матриці
Тоді систему (1) можна записати у вигляді матричного рівняння
(2)
Будемо вважати, що діагональні коефіцієнти (і = 1, 2,…, n).
Розв’яжемо перше рівняння системи (1) відносно , друге відносно і т.д. Тоді одержимо еквівалентну систему
(3)
де , при ; , при ;
; ;
Іноді кажуть, що система (3) зведена до нормального вигляду.
Введемо матриці ( та (
Систему (3) запишемо у вигляді
(4)
Систему (3) будемо розв’язувати методом послідовних наближень. За нульове наближення позначимо, наприклад, стовпчик вільних членів . Далі послідовно будуємо матриці-стовпці:
– перше наближення
– друге наближення і т.д.
Будь-яке (k + 1)-е наближення обчислюється за формулою:
, (k = 0, 1, 2, …) (5)
В розгорнутому вигляді .
Якщо послідовність наближень має границю
, (6)
то ця границя є розв’язком системи (3).
На практиці ітераційний процес припиняють, коли , де ( – гранична абсолютна похибка.
Приклад. Розв’язати систему методом простої ітерації:
.
Зведемо систему до нормального вигляду
(7)
або в матричній формі
(8)
За нульові наближення коренів системи приймаємо
.
Підставляємо ці значення в праві частини рівняння (7). Одержимо перші наближення коренів
Далі знаходимо другі і треті наближення коренів
Умови збіжності ітераційного процесу
Нехай задано зведена до нормального вигляду система лінійних рівнянь
Умова збіжності: якщо сума модулів елементів рядків або модулів елементів стовпців матриці α менша ніж 1, то процес ітерації для даної системи збігається до єдиного розв’язку незалежно від вибору вектора початкових наближень.
Для системи
або ,
де – сума модулів по стовпцях
Аналогічно можна було б перевірити виконання умови збіжності, беручи суми модулів елементів рядків.
Наведена вище умова являється достатньою, але не необхідною. Це означає, що якщо умова виконується, то процес буде збіжним. Коли ж умова не виконується, то це ще не означає, що процес буде розбіжним.
Для системи лінійних рівнянь, заданих у вигляді
,
метод простої ітерації збігається, якщо модулі діагональних коефіцієнтів для кожного рівняння системи більші, ніж суми модулів всієї решти коефіцієнтів (не враховуючи вільних членів).
ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ
Розв’язати систему лінійних алгебраїчних рівнянь методами простої ітерації.
,
Таблиця ідентифікаторів констант, змінних, процедур та функцій, використаних у програмі, та їх пояснення:
n
Константа, що задає кількість рівнянь (порядок) системи
e
Константа, що задає похибку
m
Змінна, кількість ітерацій
i
Змінна, номер рядка системи
k
Змінна, номер стовпця
kk
Змінна, що використовується для виходу з циклу
d
Змінна, яка використовується для знаходження невідомих
a
Змінна, масив, що задає кількість коефіцієнтів
b
Змінна, масив, що задає кількість вільних членів
x
Змінна, масив, що задає кількість невідомих
xx
Змінна, масив, що використовується для знаходження невідомих
write()
Функція вводу елементів
writeln()
Функція вводу елементів
read()
Функція виводу елементів
readln()
Функція виводу елементів
abs()
Функція, що повертає модуль числа
Текст програми мовою Pascal
Program prit(input,output);
const n=4;
e=0.0001;
var m,i,k,kk:integer;
d:real;
a:array[1..n,1..n]of real;
b,x,xx:array [1..n] of real;
begin
for i:=1 to n do
begin
for k:=1 to n do
begin
write('a[',i,',',k,']='...
